# coding: utf-8
# Three Sum: https://leetcode-cn.com/problems/3sum/

class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        res=[]
        l=len(nums)
        #seq表示已经排好序的列表
        seq = sorted(nums)
        print(seq)

        a=0
        while a<l-2:
            #开始双指针包夹
            b=a+1
            c=l-1
            #min-max剪枝
            maxVal=seq[l-1]+seq[l-2]
            minVal=seq[a+1]+seq[a+2]
            if seq[a]>0 or -seq[a]>maxVal or -seq[a]<minVal:
                #a去重
                while seq[a]==seq[a+1] and a<l-2:a+=1
                a+=1
                continue
            while b<c:
                if seq[a]+seq[b]+seq[c]==0:
                    res.append([seq[a],seq[b],seq[c]])
                if seq[a]+seq[b]+seq[c]>=0:
                    #c去重
                    while seq[c]==seq[c-1] and c>b:c-=1
                    c-=1
                else:
                    #b去重
                    while seq[b]==seq[b+1] and b<c:b+=1
                    b+=1
            #a去重
            while seq[a]==seq[a+1] and a<l-2:a+=1
            a+=1
        return res

# nums = [-1, 0, 1, 2, -1, -4]
nums=[-1,0,1]
sol=Solution()
res=sol.threeSum(nums)
print(res)